#pragma once

#include <array>
#include <string>
#include <string_view>
#include <vector>

namespace solution_017
{

class Solution
{
public:
    std::vector<std::string> letterCombinations(std::string digits)
    {
        if (digits.empty())
            return { };
        m_digits = digits;
        std::string path;
        backtrack(path);
        return m_comb;
    }

private:
    static std::string_view kbd(char ch) {
        using namespace std::literals::string_view_literals;
        static constexpr std::array keyboard{"abc"sv, "def"sv, "ghi"sv, "jkl"sv, "mno"sv, "pqrs"sv, "tuv"sv, "wxyz"sv};
        return keyboard.at(ch - '2');
    }

    void backtrack(std::string& path) {
        if (path.size() == m_digits.size()) {
            m_comb.push_back(path);
            return;
        }

        const auto& chs = kbd(m_digits.at(path.size()));
        for (auto ch : chs) {
            path.push_back(ch);
            backtrack(path);
            path.pop_back();
        }
    }

    std::string_view m_digits;
    std::vector<std::string> m_comb;
};

}  /* namespace solution_017 */
